|
A B+ tree is an n-ary tree with a variable but often large number of children per node. A B+ tree consists of a root, internal nodes and leaves. The root may be either a leaf or a node with two or more children.〔http://www.seanster.com/BplusTree/BplusTree.html〕 A B+ tree can be viewed as a B-tree in which each node contains only keys (not key-value pairs), and to which an additional level is added at the bottom with linked leaves. The primary value of a B+ tree is in storing data for efficient retrieval in a block-oriented storage context — in particular, filesystems. This is primarily because unlike binary search trees, B+ trees have very high fanout (number of pointers to child nodes in a node,〔 typically on the order of 100 or more), which reduces the number of I/O operations required to find an element in the tree. The NTFS, ReiserFS, NSS, XFS, JFS, ReFS, and BFS filesystems all use this type of tree for metadata indexing; BFS also uses B+ trees for storing directories. Relational database management systems such as IBM DB2,〔Ramakrishnan Raghu, Gehrke Johannes - Database Management Systems, McGraw-Hill Higher Education (2000), 2nd edition (en) page 267〕 Informix,〔 Microsoft SQL Server,〔 Oracle 8,〔 Sybase ASE,〔 and SQLite〔(SQLite Version 3 Overview )〕 support this type of tree for table indices. Key-value database management systems such as CouchDB〔(CouchDB Guide (see note after 3rd paragraph) )〕 and Tokyo Cabinet〔(Tokyo Cabinet reference )〕 support this type of tree for data access. ==Overview== The order, or branching factor, ''b'' of a B+ tree measures the capacity of nodes (i.e., the number of children nodes) for internal nodes in the tree. The actual number of children for a node, referred to here as ''m'', is constrained for internal nodes so that . The root is an exception: it is allowed to have as few as two children.〔 For example, if the order of a B+ tree is 7, each internal node (except for the root) may have between 4 and 7 children; the root may have between 2 and 7. Leaf nodes have no children, but are constrained so that the number of keys must be at least and at most . In the situation where a B+ tree is nearly empty, it only contains one node, which is a leaf node. (The root is also the single leaf, in this case.) This node is permitted to have as little as one key if necessary, and at most b. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「B+ tree」の詳細全文を読む スポンサード リンク
|